The efficiency of multiplication can be increased by converting a multiplier into a redundant binary representation, as already known in, for example, the Booth method of the 1950s. Recently, a kind of redundant binary representation, NAF, is often used to speed up cryptographic processing.
NAF is one type of redundant binary representation, and an integer k has only one corresponding NAF representation NAF(k). It has been proved that the number of non-zero digits of NAF(k) is minimum among arbitrary redundant binary representations. The average number of non-zero digits is ⅓.
In a general binary representation, either of the two numerals 0 and 1 appears in each digit position. In contrast, in NAF, one of the numerals −1, 0, and 1 appears.
The NAF representation has a feature in which at least either of two subsequent digits is 0, which is a reason for low density. Also, the name “non-adjacent form” is derived from this.
For example, a binary number 11011 (59=32+16+8+2+1 in decimal notation) is converted into a NAF representation 1000-10-1 (64−4−1=59).
Table 1 shows an example of NAF conversion of binary numbers of 4 bits or less.
TABLE 10  01  110 101110-1 100 100101 10111010-10111100-1 100010001001100110101010101110-10-11100 10-1001101 10-1011110100-10 11111000-1  
There are known several algorithms for converting an integer k into a NAF representation NAF(k). A NAF expansion is w-NAF.
The difference between w-NAF and general NAF is that w-NAF can use a wider variety of numerals for each digit. For 3-NAF, five numerals −3, −1, 0, 1, and 3 are usable. The aforementioned NAF can be regarded as 2-NAF.
Tables 2 and 3 show features of w-NAF.
Table 2 is a list of numerals used in respective NAFs.
TABLE 2Numbers Used2-NAF−1, 0, 1Three types3-NAF−3, −1, 0, 1, 3Five types4-NAF−7, −5, −3, −1, 0, 1, 3, 5, 7Nine types. . .w-NAF−2{circumflex over ( )}(w − 1) − 1, −2{circumflex over ( )}(w − 1) − 3, . . . , −1,2{circumflex over ( )}(w − 1) + 1 types0, 1, . . . , 2{circumflex over ( )}(w − 1) − 3, 2{circumflex over ( )}(w − 1) − 1
Note that “^” indicates the raising to a power. For example, 2^w means 2 to the wth power.
Table 3 is a list of non-zero digit densities in respective NAFs.
TABLE 3Density2-NAF1/33-NAF1/44-NAF1/5. . .w-NAF1/(w + 1)
w-NAF has a feature in which the number of non-zero digits among w subsequent digits is one at most. Lower density leads to a smaller number of digits to be processed. The number of clocks decreases, but many preparations are necessary, so there is a trade-off between them.